;;;求导过程，可以总结为：
;;;将模式，根据规则，生成骨架
;;;模式用来匹配源表达式
;;;骨架用于实例化为新的表达式
;;;pattern -----------rule--------> skeleton
;;;   |                                 |
;;;   |                                 |
;;;   |match                            |instantiate
;;;   |                                 |
;;;   |                                 |
;;;   V                                 V
;;;Expresssion source -----------> expression target
 
 
;;;今天要做的是，构建一门语言以及它的解释和执行方法
;;;build a language
;;;and a means of interpreting that language
;;;a means of executing that language
 
;;;与其通过将规则翻译为程序，让计算机理解并执行
;;;不如让计算机理解我们
;;;我们可以写一些程序让计算机理解这些规则
 
;;;也就是将昨天的程序（以下部分），转换为更加抽象的模式匹配程序
;;;将一个表达式对一个变量，进行求导
(define (deriv exp var)
  (cond ((constant? exp var) 0)
        ((same-var? exp var) 1)
        ((sum? exp) (make-sum (deriv (a1 exp) var)
                              (deriv (a2 exp) var)))
        ((product? exp) (make-sum (make-product (m1 exp) (deriv (m2 exp) var))
                                 (make-product (deriv (m1 exp) var) (m2 exp))))
        ...
        ))
 
(define (constant? exp var)
  (and (atom? exp)
       (not (eq? exp var))))
 
(define (same-var? exp var)
  (and (atom? exp)
       (eq? exp var)))
 
(define (sum? exp)
  (and (not (atom? exp))
       (eq (car exp) '+)))
 
(define (product? exp)
  (and (not (atom? exp))
       (eq? (car exp) '*)))
 
;;;不带化简功能的make-sum
(define (make-sum a1 a2)
  (list '+ a1 a2))
 
;;;带化简功能的make-sum
(define (make-sum a1 a2)
  (cond ((and (number? a1) (number? a2))
         (+ a1 a2))
        ((and (number? a1) (= a1 0))
         a2)
        ((and (number? a2) (= a2 0))
         a1)
        (else (list '+ a1 a2))))
 
(define a1 cadr)
(define a2 caddr)
 
(define (make-product m1 m2)
  (list '* m1 m2))
 
(define m1 cadr)
(define m2 caddr)
 
;;;以问号开头的叫模式变量
;;;冒号表示要代换的对象
;;;以冒号开头的就是骨架求值
;;;定义求导的规则列表
;;;相当于定义了一门新的语言
(define deriv-rules
  '(
    ;;规则的左边部分代表了想要匹配的求导表达式，右边部分代表了对应的值
    ;;第一条规则为：一个匹配常量的模式变量c，关于匹配任意表达式的模式变量v求导，值为0
    ;;dd的第一个参数为模式，第二个参数为当前表达式
    ((dd (?c c) (? v)) 0) ;;任何常量c对于变量v的求导为0
    ;;模式中命名为v，表达式中命名为v，因为用了同一个变量v，所以这两个值必须相同才可以
    ((dd (?v v) (? v)) 1) ;;模式是?v，匹配的模式赋值为v，当前表达式是?，匹配的表达式赋值为v
    ((dd (?v u) (? v)) 0)
    ;;模式为(+ (? x1) (? x2))，当前表达式为(? v)
    ((dd (+ (? x1) (? x2)) (? v));;;表达式x1加上表达式x2,对变量v求导
     ;;;该部分是一个骨架
     ;;;表示表达式x1对变量v求导 + 表达式x2对变量v求导
     (+ (dd (: x1) (: v)) (dd (: x2) (: v)))) 
 
    ((dd (* (? x1) (? x2)) (? v)) 
     (+ (* (: x1) (dd (: x2) (: v)))
        (* (dd (: x1) (: v)) (: x2))))
 
    ((dd (** (? x) (?c n)) (? v))
     (* (* (: n)
           (** (: x) (: (- n 1))))
        (dd (: x) (: v))))
    ))
 
;;;(* x1 x2)对变量v的求导为：x1乘以x2对变量v的求导 + x1对变量v的求导乘以x2
;;;(* x1 x2)对变量v的求导为(+ (* x1 (求导 x2 v)) (* (求导 x1 v) x2))
 
;;;在deriv-rules中，第一步要处理的是模式匹配问题
;;;pattern match
;;;foo ------------> matches exactly foo
;;;(f a b) --------> matches a list whose first element is f
;;;                                       second element is a
;;;                                       third element is b
;;;可以使用x作为名字，取得被匹配对象的值
;;;(? x) ----------> matches anything, call it x
;;;(?c x) ---------> matches constant, call it x
;;;(?v x) ---------> matches a variable, call it x
 
 
;;;在deriv-rules中,第二步要做的是骨架求值
;;;skeleton evaluation
;;;foo ------------> instantiates itself
;;;(f a b) --------> instantiates to a 3 list
;;;                  results of instantiating each of f, a and b
;;;(: x) ----------> instantiates the value of x in the matched pattern
 
 
;;;返回一个过程，该过程接受一个表达式，然后对该表达式应用求导规则进行求导
(define dsimp
  (simplifier deriv-rules))
 
;;;(dsimp '(dd (+ x y) x)) 得到的结果是 (+ 1 0)
 
;;代数操作规则
(define algebra-rules
  '(
    ;;某个运算符应用到常量e1和e2上，
    ;;其结果就是求(op e1 e2)的值
    (((? op) (?c e1) (?c e2))
     (: (op e1 e2)))
    ;;某个运算符应用到任意表达式e1和常量e2上
    ;;其结果就是把常量e2前置，变成(op e2 e1)
    (((? op) (? e1) (?c e2))
     ((: op) (: e2) (: e1)))
    ((+ 0 (? e)) (: e))
    ((* 1 (? e)) (: e))
    ((* 0 (? e)) 0)
    ;;(* e1 (* e2 x)) ===> (* (* e1 e2) x)
    ((* (?c e1) (* (?c e2) (? e3))) (* (: (* e1 e2)) (: e3)))
    ...
    ))
 
;;;首先，宏观的看，我们要做什么
;;;我们有一大堆的规则，每个规则有对应的模式和骨架（实例化的骨架）
;;;这些规则被不断应用
;;;对传入表达式的子表达式，所有的规则都需要考察一次
;;;如果有规则匹配成功，就会执行底下的这个过程
;;;模式匹配器--传入dictionary--到实例化器中，该实例化器产生一个新的表达式，
;;;然后对该新表达式进行重新检查，查看是否可以进一步化简
;;;   -----------------------
;;;  |       RULE3           |
;;;  ----------------------  |
;;; |       RULE2          | |
;;; ---------------------  | |
;;;|       RULE1         | | |
;;; ---------------------  |--
;;;|         |           | |
;;;| Pattern |  Skeleton |--
;;;|         |           |
;;; ---------------------
;;;      |              |
;;;      |(pattern应用   ----------------------------------------
;;;      |于模式匹配器)                                           |（skeleton应用于实例化器）
;;;      V                                                      V
;;;     ------------------                                --------------------------
;;;     |                | -----dictionary（字典）送入----> |                        |
;;;  -->| matcher模式匹配器|                                |instantiate（实例化器）   |
;;;  |  |                |                                |
;;;  |  ------------------                                --------------------------
;;;  |                                                                 |
;;;  |                                                                 |
;;;  -------------------------------expression(表达式)-------------------
;;;
;;;
 
 
;;;传入一个表达式
;;;进行模式匹配
;;;匹配成功某个规则，传递字典，进行化简，得到新的表达式，从头开始，再次匹配
;;;匹配失败，匹配下一个规则
;;;指到匹配完所有的规则
 
 
 
;;;模式匹配器
;;;                            |
;;;                            |输入pattern
;;;                            V
;;;                     ----------------
;;;                    |                |
;;; ---输入expression-->|  matcher匹配器  |-----输出dictionary-->
;;;                    |                |
;;;                     ----------------
;;;                            ^
;;;                            |输入dictionary
;;;                            |
 
 
;;;模式匹配器的宏观结构
(define (match pat exp dict)
  (cond ((eq? dict 'failed) 'failed)
        ((atom? pat) ... ) ;;atomic patterns
        ;;如果pat不是atom，说明是包含变量，如果exp为atom，那就是failed
        ((atom? exp) 'failed)
        (else
         (match (cdr pat) (cdr exp)
           (match (car pat) (car exp) dict) ;;匹配car部分，产生一个新的dict
           ))))
 
;;(+ (* (? x) (? y)) (? y)) 模式串
;;(+ (* 3 x) x) 实际的表达式
 
((atom? pat)
 (if (atom? exp)
     (if (eq? pat exp)
         dict
         'failed)
     'failed))
 
;;(?c x) 匹配任意常量
((arbitrary-constant? pat)
 (if (constant? exp)
     (extend-dict pat exp dict)
     'failed))
;;(?v x) 匹配任意变量
((arbitrary-variable? pat)
 (if (variable? exp)
     (extend-dict pat exp dict)
     'failed))
;;(? x) 匹配任意表达式
((arbitrary-expression? pat)
 (extend-dict pat exp dict))
 
 
;;;实例化器
;;;                         |
;;;                         |skeleton
;;;                         v 
;;;                -------------------
;;;                |                  |
;;;---dictionary-->|  Instantiate     | ---expression-->
;;;                |                  |
;;;                --------------------
;;;
;;;
 
(define (instantiate skeleton dict)
  (define (loop s)
    (cond ((atom? s) s)
          ;;在规则中，以冒号开头的就是骨架求值
          ;;这是程序中定义的抽象语法
          ((skeleton-evaluation? s) (evaluate (eval-exp s) dict))
          ((else (cons (loop (car s)) (loop (cdr s)))))))
  (loop skeleton))
 
 
(define (evaluate form dict)
  (if (atom? form)
      (lookup form dict)
      (apply (eval (lookup (car form) dict) user-initial-environment)
             (mapcar (lambda (v)
                       (loopup v dict))
                     (cdr form)))))
 
;;;控制结构
;;;GIGO
 
;;化简器输入一些规则，并根据这些规则生成一个使用该规则进行化简的procedure
(define (simplifier the-rules)
  ;;;化简一个表达式
  (define (simplify-exp exp)
    ... )
  ;;;化简表达式的子部分
  (define (simplify-parts exp)
    ... )
  (define (try-rules exp)
    ... )
  simplify-exp)
 
(define (simplify-exp exp)
  (try-rules (if (compound? exp)
                 (simplify-parts exp)
                 exp)))
 
(define (simplify-parts exp)
  (if (null? exp)
      '()
      (cons (simplify-exp (car exp))
            (siplify-parts (cdr exp)))))
 
;;;上面这两个procedure可以改写为
(define (simplify-exp exp)
  (try-rules (if (compound? exp)
                 (map simplify-exp exp)
                 exp)))
 
 
;;;这里的exp就是最初表达式的子表达式
(define (try-rules exp)
  (define (scan rules)
    ... )
  (scan the-rules))
 
 
;;好的编程或者是设计方法需要知道，什么是不需要考虑的
;;比如这里的simplify-exp，不需要知道它是怎么实现的，只需要知道它会返回化简后的结果就可以了
(define (scan rules)
  (if (null? rules)
      exp
      (let ((dict (match (pattern (car rules)) exp (empty-dictionary))))
        (if (eq? dict 'failed)
            (scan (cdr rules))
            (simplify-exp (instantiate (skeleton (car rules)) dict))))))
 
(define (empty-dictionary) '())
(define (extend-dictionary pat dat dict)
  ;;取出模式中变量的名字
  (let ((name (variable-name pat)))
    ;;查找字典中该名字对应的值
    (let ((v (assq name dict)))
      (cond ((null? v) (cons (list name dat) dict))
            ;;如果字典中存在，且与当前值相等
            ((eq? (cadr v) dat) dict)
            (else 'failed)))))
(define (lookup var dict)
  (let ((v (assq var dict)))
    (if (null? v)
        var
        (cadr v))))
 
 
;;;总结：
;;;整体流程为：
;;;首先根据求导的各种情况，分别定义各种规则deriv-rules
;;;每个规则由两部分构成，一部分为模式，另一部分是骨架，因此分别对应两个处理器，一个是模式匹配器，一个是根据骨架的实例化器
;;;通过化简器simplifier来根据这些规则，化简表达式exp，
;;;因此，化简器的输入为这些规则，输出为一个参数为exp的procedure（该procedure的输入为exp）simplify-exp
;;;该化简器中，使用这些规则不断的匹配表达式
;;;如果匹配上，将匹配的结果放入字典中，扩充字典，返回字典；然后使用实例化器，实例化对应的骨架，
;;;递归化简实例化后的表达式(simplify-exp (instantiate (skeleton (car rules)) dict))
;;;如果没有匹配上，继续匹配下一条规则，直到所有的规则匹配完成
 
 
;;;这里的递归模式非常复杂，
;;;最重要的事情就是：不要去思考它
;;;如果去思考它的实际行为，大家就会迷惑
;;;the key to this ---
;;;it's very good programming and very good design
;;;is to know what not to think about
 
;;;以前最大的问题就是，去思考它了，浪费了太多的时间
 
(assq 5 '((2 3) (5 7) (11 13)))
 
;;;转化为自己的方式：
;;;求导的左边对应的是各种情况，右边对应的是相应的求导结果
;;;============================================
;;;一种实现思路是：将各种情况翻译为程序，让计算机执行，对应上一节的实现方式
;;;另一种实现思路是：让计算机跟我们的思路保持一致，让计算机理解这些规则，对应这节的模式匹配
;;;================
;;;观察求导的各种情况，制定求导的规则
;;;规则左边对应各种模式（对应求导的左边）
;;;规则右边对应实例化的骨架（对应求导的右边）
;;;实现相应的模式匹配器和骨架实例化器
;;;模式匹配器匹配后，将匹配的结果放入字典中，将该字典送入骨架实例化器中进行实例化
;;;化简器作为入口，不断的用各种规则匹配表达式来进行化简，直到无法化简（也就是没有任何规则可以匹配）
